package class05_06_mergeSortRelated;
/*
* 找出所有左侧数比右侧数小的数的和
* 比如 1 5 2 3,6
* 1+2+(1+5+2+3)
* */

public class SmallSum {
    public static int mergeAndGetSmallSum(int[] arr,int l, int m, int r){
        /*
        * l = start of arr1
        * m = end of arr1
        * r = end of arr2
        * */
        int sum = 0;
        int[] temp = new int[r-l+1];
        int pointer1 = l;
        int pointer2 = m+1;
        int pointerMerge = 0;

        while(pointerMerge<=r-l){
            if(pointer1>m){
                temp[pointerMerge] = arr[pointer2++];
            }else if(pointer2>r){
                temp[pointerMerge] = arr[pointer1++];
            } else if (arr[pointer1]<arr[pointer2]) {
                temp[pointerMerge] = arr[pointer1];
                sum += (r-pointer2+1)*arr[pointer1];
                pointer1++;
            } else {
                temp[pointerMerge] = arr[pointer2++];
            }

            pointerMerge++;
        }

        for (int i = 0; i<temp.length; i++){
            arr[l+i] = temp[i];
        }
        return sum;
    }

    public static int mergeSortAndSmallSum(int arr[]){
        int group_size=1;
        int sum = 0;



        while(group_size<arr.length){
            int l = 0;
            int r = l+2*group_size-1;
            int m = (l+r)/2;
            while(m+1<arr.length){
                if (r>=arr.length) {sum += mergeAndGetSmallSum(arr,l,m,arr.length-1);}
                else {sum += mergeAndGetSmallSum(arr,l,m,r);}

                l = r+1;
                r = l+(2*group_size)-1;
                m = (l+r)/2;
            }
            group_size*=2;
        }
        return sum;
    }

    public static int smallSumN2(int arr[]){
        int sum = 0;
        for(int i = 0; i<arr.length; i++){
            for (int j = 0; j<i; j++){
                if (arr[j]<arr[i]){
                    sum += arr[j];
                }
            }
        }
        return sum;
    }

    //for test
    public static int[] randomArr (int maxLen,int maxValue)
    {
        int len = (int)(maxLen*Math.random());
        int[] arr =new int[len];

        for(int i = 0; i<len; i++)
        {
            arr[i] = (int)(maxValue*Math.random());
        }
        return arr;
    }

    //for test
    public static boolean isOrder(int[] arr)
    {
        int len = arr.length;

        for(int i = 0; i<len-1; i++)
        {
            if(arr[i+1]<arr[i])
            {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = randomArr(100,100);
        //for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
        System.out.println(smallSumN2(arr));
        System.out.println(mergeSortAndSmallSum(arr));
        //for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
        System.out.println(isOrder(arr));
    }
}
